1. Field of the Invention
The present invention relates to data memories and more particularly, to a content addressable memory that receives a pattern string of any length.
2. Description of the Related Art
Content addressable memory (hereinafter referred to as CAM) is a special type of computer memory used in certain very high speed searching applications. For example, CAM is commonly used in a network intrusion detection system to match the content of packets, filtering malicious packets. However, conventional CAMs simply can match a fixed length of pattern strings while the length of a pattern string in a network intrusion detection system is variable.
FIG. 1 is a block diagram of a CAM according to the prior art. As illustrated, a conventional CAM 300 comprises a storage list 310, a search word register 320 and an encoder 330. Inputted search word is stored in the search word register 320 for matching with the pattern string 0˜n in the storage list 310. The length of one pattern string consist of 32˜144 bits (4˜18 bytes).
The storage list 310 of a typical CAM has hundreds to 32K items, and the relative address line consists of 7 bits to 15 bits. Every storage word has a respective match-line for indicating match case or mismatch case between the search word and the storage pattern string. The output of the match-line is sent to the encoder 330 that outputs a binary match address corresponding to the match-line through a signal M_RES.
Because there may be many words matched in the content addressable memory 300, the encoder 300 is usually a priority encoder but not a simple encoder. The priority encoder selects the highest priority match address to map the matched result. Normally, a word at a lower address has a relatively higher priority. Further, the encoder 330 outputs a signal HIT to indicate whether or not matched. Basically, the function of the content addressable memory 300 is to receive a search word, and then to send back the matched memory address. The content addressable memory 300 can be regarded as a programmable device to map an inputted large space search word onto a small space output match address.
According to the aforesaid conventional content addressable memory 300, the storage list 310 can only store pattern strings of a fixed length, for example, 36 bits˜144 bits. In actual practice, pattern strings have different lengths. When storing relatively shorter pattern strings, the rest memory space will be a waste of space. On the contrary, pattern strings that are longer than the width of the storage list 310 will be cut off. In conclusion, the aforesaid conventional content addressable memory 300 has the drawbacks of: 1. wasting hardware space, and 2. unable to match long pattern strings.